package com.hqq.leetcode.tree;

import com.hqq.exercise.tree.TreeNode;
import com.hqq.exercise.tree.TreeNodeUtil;

/**
 * Convert BST to Greater Tree 二叉排序树转化成更大树
 * 题目描述:
 * Given a Binary Search Tree (BST), convert it to a Greater Tree
 * such that every key of the original BST is changed to the original
 * key plus sum of all keys greater than the original key in BST.
 * 样例输入:
 * Given a binary search Tree ｀{5,2,13}`:
 * 5
 * /   \
 * 2     13
 * 样例输出:
 * Return the root of new tree
 * 18
 * /   \
 * 20     13
 * 思路:
 * 反向中序遍历可以得到一个从大到小的序列(右->中->左)
 * 然后进行累加即可 ORZ
 * Created by heqianqian on 2017/9/12.
 */
public class ConvertBST {

    private int sum = 0;

    public static void main(String[] args) {
        /*data preparation*/
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(2);
        root.right = new TreeNode(13);

        ConvertBST convertBST = new ConvertBST();
        convertBST.convert(root);
        TreeNodeUtil.preOrderTraversal(root);
    }

    /**
     * 把BST树转换成更大树
     */
    private void convert(TreeNode root) {
        if (root == null) {
            return;
        }
        convert(root.right);
        root.val = root.val + sum;
        sum = root.val;
        convert(root.left);
    }

}
